package org.algorithm.落雪.数组.三月.第二周;

import java.util.Arrays;

/**
 * @author 落雪
 * @date 2022/03/08 11:38 PM
 * @description:        周四作业
 *
 *  <p>
 *      给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
 *
 *      返回追加到 nums 中的 k 个整数之和。
 *
 *      案例：
 *          输入：nums = [1,4,25,10,25], k = 2
 *          输出：5
 *          解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
 *          nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
 *          所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。
 *  </p>
 *
 * uri:  https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum/
 */
public class 向数组中追加K个整数 {

    public static void main(String[] args) {
        int[] nums = {1,4,25,10,25};
        System.out.println(minimalKSum(nums, 2));
    }


    public static long minimalKSum(int[] nums, int k) {

        Arrays.sort(nums);
        long ans = 0,start = 1;
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (start < nums[i]) {
                int cnt = Math.min((int) (nums[i] - start), k);
                ans += (2L * start + cnt - 1) * cnt / 2;
                k -= cnt;
            }
            start = nums[i] + 1;
        }

        if (k > 0) {
            ans +=(2L * start + k -1) * k / 2;
        }
        return ans;
    }
}
